ON THE ISSUE OF THE ELEMENTS NUMBER IN THE GATE,
REALIZING THE GENERALIZED VOTING FUNCTION

Alekhina Marina Anatol'evna, Doctor of physical and mathematical sciences, professor, head of sub department of discrete mathematics, Penza State University (Penza, 40 Kransaya str.), alehina@pnzgu.ru

519.718

The article relates to the one of the most important topics of mathematical cybernetics – to the theory of synthesis, reliability and complexity of control systems.
Topicality of research in this field is determined by the significance of multiple applications, appearing in different fields of science and technology. All the variety of digital technologies: computers, microprocessor systems of technological processes measurements and automation, digital communication and television etc., are based on the same elements including extremely different in complexity microschemes – from logical elements, executing primitive operations, to complex programmed crystals, containing millions of logical elements. Logical elements of digital devices to a large extent determine the functional features of the latter, construction, technological effectiveness and reliability thereof. The list of general modeling objects of the mathematical theory of synthesis, complexity and reliability of control systems includes gates with unreliable functional elements, realizing Boolean functions. In a number of results, relating to realization of Boolean functions by reliable gates with unreliable elemenets, there appears the Ngˆ parameter – minimal number of functional elements required for realization of the voting function x` in the considered complete basis. It has been revealed that the other functions (let us letter them G) also possess features similar to voting function features. These functions have the following form x1 x2 x1 x3 x2 x3 σ σ ∨ σ σ ∨ σ σ ( {0,1} σi ∈ , i∈{1,2,3}) and are designated in the article as generalized voting functions, i.e. G is the set of functions of x1 x2 x1 x3 x2 x3 σ σ ∨ σ σ ∨ σ σ form. Let Ng be the minimal number of absolutely reliable functional elements, required for realization of g ∈ G function in the considered complete basis, and G min g g G N N ∈ = , i.e. NG is the minimal number of absolutely reliable functional elements, sufficient for realization of at least one function from G set in the considered complete basis. The article aims at deriving the upper bound of NG, that would be true in the arbitrary complete basis. It is presupposed that all functional elements of the basis are absolutely reliable. To obtain NG upper bound the author uses the same methods and approaches, as for proving the wellknown Post’s theorem about the completetion of Boolean functions. It is proved that in the arbitrary complete finite basis at least one function from G set may be realized by the gate, containing at most eight functional elements. Using this feature, it is
possible to substitute NG with 8 constant. In the previously achieved results on reliability of gates, consisting of unreliable functional elements and containing NG that depends on the considered basis, it is possible to improve the number of previously known reliability estimations of gates asymptotically optimal in reliability.

functional elements, synthesis of combinatorial gates composed of functional elements.

1. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku [Introduction into discrete mathematics]. Moscow: Vyssh. shk., 2001, 384 p.
2. Lupanov O. B. Asimptoticheskie otsenki slozhnosti upravlyayushchikh sistem [Asymptotic evaluation of control systems complexity]. Moscow: Izd-vo MGU, 1984, 138 p.
3. Alekhina M. A., Epifanov S. Yu. Molodezhnaya matematicheskaya nauka. 2012: sb. materialov Vserossiyskoy s Mezhdunar. uchastiem molodezhnoy nauchno-prakticheskoy konf. [Youth mathematical science 2012: proceedings of the All-Russian and International youth scientific-practical conference]. Saransk: Izd-vo Mordovskogo gos. ped. instituta imeni M. E. Evsev'eva, 2012, pp. 94–96.
4. Aksenov S. I. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Estestvennye nauki [University proceedings. Volga region. Natural sciences]. 2005, no. 6 (21), pp. 42–55.
5. Alekhina M. A. Diskretnaya matematika [Discrete mathematics]. 2012, vol. 24, no. 3, pp. 17−24.
6. Alekhina M. A. Problemy avtomatizatsii i upravleniya v tekhnicheskikh sistemakh 2011: tr. Mezhdunar. nauch.-tekhn. konf. [Issues in automation and control in technical systems 2011: proceedings of the International scientific and technical conference]. Penza: Izd-vo PGU, 2011, vol. 1, pp. 91–93.
7. Red'kin N. P. Matematicheskie voprosy kibernetiki: sb. st. [Mathematical problems in cybernetics: collected papers]. Moscow: Nauka, 1989, vol. 2, pp. 198–222.